1. Technical Field
This disclosure relates to integrated circuit design, and more particularly to physical routing of wires on integrated circuits.
2. Description of the Related Art
In modern integrated circuit design, wire routing and wire length has become of paramount importance as device geometries continue to shrink. Accordingly, in an effort to use the shortest wire lengths possible, electronic design automation tools have been developed to optimize wire lengths in complex circuit designs.
In the realm of physical wire routing it is sometimes necessary to interconnect a number of nodes using the shortest wire lengths. Mathematically, this problem may be stated in terms of determining the minimum Steiner tree of a graph. As such, much work has been done to create algorithms that use variants of the Steiner tree. More particularly, there have been several algorithms developed that solve a rectilinear Steiner minimum tree (RSMT) problem.
These conventional RSMT algorithms solve the wire length problem using a variety of techniques. For example, one such rectilinear Steiner minimum tree technique is known a fast look up table estimation (FLUTE), which uses a pre-computed look up table. Another conventional technique is known as a node-breaking technique. These conventional techniques can accurately create an RSMT construction. However, they do have drawbacks. For example, when using look up tables there is inflexibility, particularly in designs that have pre-routes, or routes that have been routed by the designer ahead of time. In addition, some conventional RSMT algorithms do not easily accommodate sink-driver constraints.